%-------------------------------
%同余习题
%-------------------------------
		\begin{Exercise}\label{exer:43}
			设模m=16,求解1,9,16,17,25,160模16余数,并找出同余的数来。
		\end{Exercise}
		\jd{
			依次计算上面各数模16的余数，余数分别为1、9、0、1、9、0,根据同余定义，我们有$1 \equiv 17 (mod \ 16),9 \equiv 25 (mod \ 26),16 \equiv 160 (mod \ 26)$。
		}
		\begin{Exercise}
			求$7^{2046}$写成十进制数时的个位数。
		\end{Exercise}
		\jd{答案是：9,计算过程如下：\par
			$7^2=49\equiv 9(mod  10), 9^2 =81 \equiv 1(mod  10),2046=4 \times 511+2 \Rightarrow 7^{2046} \equiv ((7^2)^2)^{511} \times 7^2 \equiv 9 (mod  10)$
		}
		\begin{Exercise}
			求$2^{1000}$的十进制表示中的末尾两位数字。
		\end{Exercise}
		\jd{答案为：76，计算过程如下：\par
			$
			2^ 0 = 1 (mod 100),
			2^ 1 = 2 (mod 100),
			\uwave{2^ 2 = 4 (mod 100)},
			2^ 3 = 8 (mod 100),
			2^ 4 = 16 (mod 100)\\
			2^ 5 = 32 (mod 100),
			2^ 6 = 64 (mod 100),
			2^ 7 = 28 (mod 100),
			2^ 8 = 56 (mod 100),
			2^ 9 = 12 (mod 100)\\
			2^ {10} = 24 (mod 100),
			2^ {11} = 48 (mod 100),
			2^ {12} = 96 (mod 100),
			2^ {13} = 92 (mod 100),
			2^ {14} = 84 (mod 100)\\
			2^ {15} = 68 (mod 100),
			2^ {16} = 36 (mod 100),
			2^ {17} = 72 (mod 100),
			2^ {18} = 44 (mod 100),
			2^ {19} = 88 (mod 100)\\
			2^ {20} = 76 (mod 100),
			2^ {21} = 52 (mod 100),
			\uwave{2^ {22} = 4 (mod 100)},
			2^ {23} = 8 (mod 100),
			2^ {24} = 16 (mod 100)\\
			2^ {25} = 32 (mod 100),
			2^ {26} = 64 (mod 100),
			2^ {27} = 28 (mod 100),
			2^ {28} = 56 (mod 100),
			2^ {29} = 12 (mod 100)\\
			2^ {30} = 24 (mod 100),
			2^ {31} = 48 (mod 100),
			2^ {32} = 96 (mod 100),
			2^ {33} = 92 (mod 100),
			2^ {34} = 84 (mod 100)\\
			2^ {35} = 68 (mod 100),
			2^ {36} = 36 (mod 100),
			2^ {37} = 72 (mod 100),
			2^ {38} = 44 (mod 100),
			2^ {39} = 88 (mod 100)\\
			$
			$1000=20\times 50 \Rightarrow 2^{1000}={2^{20}}^50 \equiv 2^{20} \equiv 76 (mod\ 100)$
		}
		\begin{Exercise}
			已知2019年9月29日是星期天，问之后的$2^{100}$天是星期几？第$2^{200}$天呢？
		\end{Exercise}
		\jd{
			由于$2^1 \equiv 2(mod\ 7),2^2 \equiv 4 (mod\ 7),2^3 \equiv 1(mod\ 7)$\par
			所以$2^{3\times 33} \equiv 1 (mod\ 7)$\par
			又因为$100=3 \times 33 +1$,所以$2^{100}=2^{3 \times 33 +1}=2^{3\times 33} \times 2 \equiv 2 (mod\ 7)$，所以第$2^{100}$天是星期三。
			同理$200=3\times 66+2$,$2^{200}=2^{3 \times 66 +2}=2^{3\times 66} \times 2^2 \equiv 4 (mod\ 7)$,所以第$2^{200}$天是星期五.
		}
		\begin{Exercise}
			求$1^5 +2^5 +3^5 + \ldots + 99^5$之和被4除的余数。
		\end{Exercise}
		\jd{
			$4^5+5^5+6^5+7^5 \equiv 0+1^5+2^5+3^5 (mod  4)\\
			\ldots \\
			96^5+97^5+98^+99^5 \equiv 0+1^5+2^5+3^5 (mond  4)$共有24组，$24 \times (1+32+3^5) \equiv 0 (mod  4)$
		}
		\begin{Exercise}
			写出模9的一个完全剩余系，它的每个数都是奇数。
		\end{Exercise}
		\jd{
			$\left\lbrace 0,1,2,3,4,5,6,7,8\right\rbrace ,2k+1,\left\lbrace 1,3,5,7,9,11,13,15,17\right\rbrace $
		}
		
		\begin{Exercise}
			写出模9的一个完全剩余系，它的每个数都是偶数。
		\end{Exercise}
		\jd{
			$\left\lbrace 0,1,2,3,4,5,6,7,8\right\rbrace ,2k,\left\lbrace 0,2,4,6,8,10,12,14,16\right\rbrace $
		}
		
		\begin{Exercise}
			用模5和模6的完全剩余系，表示模30的完全剩余系。
		\end{Exercise}
		
		\jd{
			模5的完全剩余系
			$\left\lbrace 0,1,2,3,4 \right\rbrace $\par
			模6的完全剩余系$\left\lbrace 0,1,2,3,4,5 \right\rbrace $\par
			5，6互质,$30=5 \times 6$\par
			$
			m_i \times 5 + n_j \times 6,\left\lbrace 
			0,1,2,3,4,5,
			11,17,23,29,35,
			10,16,22,28,34,40,
			15,21,27,31,39,45,
			20,26,32,38,44,50 \right\rbrace 
			$
		}
		
		\begin{Exercise}
			写出12的最小正缩系。
		\end{Exercise}
		\jd{
			最小正完全系\{ 1,2,3,4,5,6,7,8,9,10,11,12 \},与12互素的有\{1,5,7,11\}
		}
		\begin{Exercise}
			用模5和模6的缩系，表示模30的缩系。
		\end{Exercise}
		\jd{
			5和6互素,x和y遍历5和6的缩系，$5x+6y$也遍历模$5 \times 6$的缩系。模5的缩系$\left\lbrace 1,2,3,4 \right\rbrace $，模6的缩系$\left\lbrace 1,5 \right\rbrace $，模30的缩系$
			11,16,21,30,
			35,40,45,50
			$
		}
		\begin{Exercise}
			计算以下整数的欧拉函数。\par
			(1)24 \hspace{1cm}(2)64 \hspace{1cm}(3)187 \hspace{1cm}(4)360 \hspace{1cm}
		\end{Exercise}
		\begin{Exercise}
			计算$8 \times 9 \times 10 \times 11 \times 12 \times 13 (mod \  7)$.
		\end{Exercise}
		\jd{
			$\because 8 \equiv 1 (mod \ 7)\\
			9 \equiv 2 (mod \ 7)\\
			10 \equiv 3 (mod \ 7)\\
			11 \equiv 4 (mod \ 7)\\
			12 \equiv 5 (mod \ 7)\\
			13 \equiv 6 (mod \ 7)\\
			\therefore 720 \equiv 6 (mod \ 7)\\
			$
		}
		
		\begin{Exercise}
			求$229^{-1}(mod \ 281)$
		\end{Exercise}
		\jd{
			229模281逆元是27.\\
			具体解法是首先判断$gcd(229,281)=1$，逆元存在，然后利用扩展欧几里得算法求逆元$s_i=s_{i-2}+q_{i-1}s_{i-1},t_i=t_{i-2}+q_{i-1}t_{i-1}$：\\
			\begin{tabular}{|c|c|c|c|c|}
				\hline 
				i& $r_i$ & $q_i$ & $s_i$ & $t_i$ \\ 
				\hline 
				0& 281 & - & 1 & 0 \\ 
				\hline 
				1& 229 & 1 & 0 & 1 \\ 
				\hline 
				2& 52 & 4 & 1 & -1 \\ 
				\hline 
				3& 21 & 2 & -4 & 5 \\ 
				\hline
				4& 10 & 2 & 9 & -11 \\ 
				\hline
				5& 1 & 10 & -22 & 27 \\ 
				\hline
				5& 0 & - & - & - \\ 
				\hline
			\end{tabular} 
			
			%		我们先用sagemath直接求解一下：\\
			%		$\begin{verbatim}
			%			sage: 229.inverse_mod(281)
			%			27
			%			sage:
			%		\end{verbatim}$
		}
		
		\begin{Exercise}
			求$3169^{-1} (mod\ 3571)$.
		\end{Exercise}
		\jd{
			利用欧几里得扩展算法计算，计算结果为：2887.\\
			sagemath验证语句：3169.inverse\_mod(3571)
		}
		
		\begin{Exercise}
			解方程$105x+121y=1(x,y \in \mathbb{Z})$.
		\end{Exercise}
		\jd{根据欧几里得扩展算法，我们有$gcd(r_0,r_1)=s_nr_0+t_nr_1$，我们设$r_0=121,r_1=105$,同时我们可知105与121互素($gcd(121,105)=1$)，可见欧几里得扩展算法最后的等式为$121s_n+105t_n=1$，与所求的方程相同，我们利用扩展欧几里得算法进行计算：\par
			\begin{tabular}{|c|c|c|c|c|}
				\hline 
				& $r_i$ & $q_i$ & $s_i$ & $t_i$ \\ 
				\hline 
				0& 121 & - & 1 & 0 \\ 
				\hline 
				1& 105 & 1 & 0 & 1 \\ 
				\hline 
				2& 16 & 6 & 1 & -1 \\ 
				\hline 
				3& 9 & 1 & -6 & 7 \\ 
				\hline 
				4& 7 & 1 & 7 & -8 \\ 
				\hline 
				5& 2 & 3 & -13 & 15 \\ 
				\hline 
				6& 1 & 2 & 46 & -53 \\ 
				\hline 
				7& 0 &  &  &  \\ 
				\hline 
			\end{tabular} 
		}
		\begin{Exercise}
			求解一次同余方程$27x \equiv 12(mod\ 15)$
		\end{Exercise}
		\jd{
			gcd(27,15)=3，所以同余方程共有3个解，同余方程$9x\equiv 4 (mod\ 5)$的一个特解是x=1,所以原方程全部解为$x\equiv 1+\frac{15}{3}t(mod\ 15),t\in {0,1,2}$，求得其解为1，6，11.
		}
		
		\begin{Exercise}
			求解一次同余方程$24x \equiv 6(mod\ 81)$
		\end{Exercise}
		\jd{
			gcd(24,81)=3，所以同余方程共有3个解，同余方程$8x\equiv 2 (mod\ 27)$的一个特解是x=7,所以原方程全部解为$x\equiv 7+\frac{81}{3}t (mod\ 81),t\in {0,1,2}$，求得其解为7,34,61.
		}
		
		\begin{Exercise}
			求解一次同余方程$91x \equiv 26(mod\ 169)$
		\end{Exercise}
		\jd{
			gcd(91,169)=13，并且$13 \mid 26$,所以同余方程共有13个解，同余方程$7x\equiv 2 (mod\ 13)$的一个特解是x=4(可以通过遍历的方法求得),所以原方程全部解为$x\equiv 4+\frac{169}{13}t (mod\ 169),t\in {0,1,2,3,4,5,6,7,8,9,10,11,12}$，求得其解为4,17,30,43,56,69,82,95,108,121,134,147,160.
		}
		
		%	\begin{Exercise}
		%		求解一次同余方程$71x \equiv 32(mod\ 3441)$ %这道题要算欧拉函数
		%	\end{Exercise}
		%	\jd{
		%		gcd(71,3441)=1，所以同余方程有唯一解，$x\equiv 32 \times 71^{\varphi(3441)-1} (mod\ 3441),\varphi(3441)=2160 \Rightarrow x \equiv 2084(mod\ 3441)
		%	}
		
		\begin{Exercise}
			确定以下同余式不同解的个数，无须求出具体解。
			\begin{enumerate}
				\item $72x \equiv 47(mod\ 200)$
				\item $4183x \equiv 5781(mod\ 15087)$
				\item $1537x \equiv 2863(mod\ 6731)$
			\end{enumerate}
		\end{Exercise}
		\jd{
			gcd(72,200)=8,但是$8 \nmid 47$,所以第一个方程无解。gcd(4183,15087)=47，且$47 \mid 5781$，故第二方程有解，且解的个数为47.gcd(1537,6731)=53,但是$53 \nmid 2863$，故此方程无解。
		}
		
		\begin{Exercise}
			求解同余方程组：
			$
			\begin{cases}
			x\equiv 9(mod\ 12)\\
			x \equiv 6(mod\ 25)\\	
			\end{cases}
			$
		\end{Exercise}
		\jd{
			gcd(12,25)=1,利用中国剩余定理，唯一解为$x \equiv 25\times 1 \times 9+12\times 23 \times 6 (mod\ 12\times 25) \equiv 1881 \equiv 81(mod\ 300) $
		}
		
		\begin{Exercise}
			求解同余方程组：
			$
			\begin{cases}
			x\equiv 5(mod\ 7)\\
			x \equiv 12(mod\ 15)\\
			x \equiv 18(mod\ 22)\\	
			\end{cases}
			$
		\end{Exercise}
		\jd{
			$gcd(7,15)=1,gcd(15,22)=1,gcd(7,22)=1$，可以看出以上方程组的模两两互素，根据中国剩余定理，我们有:\par
			$x \equiv 5(mod\ 7),m=7\times 15 \times 22=2310$\\
			$M_1 = 15 \times 22 = 330, M_1' = 1 (mod\ 7)$\\
			$M_2=7*22=154,M_2'=4(mod\ 15)$\\
			$M_3=7*15=105,M_3'=13(mod\ 22)$\\
			$x=M_ 1 M_1' b_1+M_2 M_2' b_2+M_3 M_3' b_3=15\times 1 \times 5+154 \times 4 \times 12+105 \times 13 \times 18 (mod\ 2310) \equiv 1272 (mod\ 2310)$
			
			%		%利用sagemath验证结果
			%		print "M_1=",15*22,"M_1'=",(15*22).inverse_mod(7)
			%		print "M_2=",7*22,"M_2'=",(7*22).inverse_mod(15)
			%		print "M_3=",15*7,"M_3'=",(15*7).inverse_mod(22)
			%		a=15*22*(15*22).inverse_mod(7)*5+7*22*(7*22).inverse_mod(15)*12+15*7*(15*7).inverse_mod(22)*18
			%		b=mod(a,7*15*22)
			%		print mod(a,7*15*22)
			%		print "idea:5",mod(b,7)
			%		print "idea:12",mod(b,15)
			%		print "idea:18",mod(b,22)
		}
		\begin{Exercise}
			求解同余方程组：
			$
			\begin{cases}
			x\equiv 5(mod\ 9)\\
			3x \equiv 12(mod\ 5)\\
			4x \equiv 18(mod\ 7)\\	
			\end{cases}
			$
		\end{Exercise}
		\jd{
			先看$3x \equiv 12(mod\ 5)$的解，由于$gcd(3,5)=1$，所以$x\equiv 12 \times 3^{\varphi(5)-1} \equiv 12 \times 3^3 \equiv 324 \equiv 4 (mod\ 5)$\par
			再看$4x \equiv 18(mod\ 7)$的解，由于$gcd(4,7)=1$，所以$x\equiv 4 \times 18^{\varphi(7)-1} \equiv 4 \times 18^5 \equiv 1 (mod\ 5)$\par
			也可以直接化简为以下方程组。\par
			方程组等价于：\par
			$
			\begin{cases}
			x\equiv 5(mod\ 9)\\
			x \equiv 4(mod\ 5)\\
			x \equiv 1(mod\ 7)\\	
			\end{cases}
			$
			\par
			由于9,5,7两两互素，根据中国剩余定理计算可得x=239.
			%		%用sagemath求解
			%		print crt(5,4,9,5)
			%		print crt(23,1,45,7)
			%		print "idea 5:",mod(113,9)
			%		print "idea 3:",mod(113,5)
			%		print "idea 1:",mod(113,7)
		}
		
		\begin{Exercise}
			有总数不满50人的一队士兵，一至三报数，最后一人报一，一至五报数，最后一人报二，一至七报数，最后一人报二，这支队伍共有士兵多少人。
		\end{Exercise}
		\jd{
			根据题意列出方程：\par
			$
			\begin{cases}
			x\equiv 1(mod\ 3)\\
			x \equiv 2(mod\ 5)\\
			x \equiv 2(mod\ 7)\\	
			\end{cases}
			$
			\par
			3,5,7两两互素，根据中国剩余定理，$m=3 \times 5\times 7=105,M_1=35,M_1'=2,M_2=21,M_2'=1,M_3=15,M_3'=1,x\equiv 35\times 2\times 1+ 21\times 1 \times 2 +15 \times 1 \times 2 \equiv 142 \equiv 37 (mod\ 105)$
			%sagemath 验证
			%		print "idea 1:",mod(37,3)
			%		print "idea 2:",mod(37,5)
			%		print "idea 2:",mod(37,7)
			%结果
			%		sage: print "idea 1:",mod(37,3)
			%		....: print "idea 2:",mod(37,5)
			%		....: print "idea 2:",mod(37,7)
			%		....:
			%		idea 1: 1
			%		idea 2: 2
			%		idea 2: 2
			%		sage:
			
		}
